package zuochengyun;

import list.LinkedListCreate;
import list.ListNode;

/**
 * 判断链表是否是回文结构
 * 
 * @author Administrator
 */
public class ListIsPalindrome {

	public static void main(String[] args) {
		int[] array = { 1, 3, 8, 6, 8, 3, 1};
		ListNode head = LinkedListCreate.createList(array);
		System.out.println(isPalidrome(head));
		LinkedListCreate.printList(head);
	}

	public static boolean isPalidrome(ListNode head) {
		if (head == null || head.next == null) {
			return true;
		}
		// 首先找到中间结点,如果是偶数的话，比如8，要是第4个结点
		ListNode fast = head;
		ListNode slow = head;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		fast = slow.next; // 右半部分的第一个结点
		ListNode pre = null, next = null;
		while (fast != null) {
			next = fast.next;
			fast.next = pre;
			pre = fast;
			fast = next;
		}
		boolean result = true;
		ListNode node1 = head, node2 = pre;
		// 判断是否是回文结构
		while (node1 != null && node2 != null) {
			if (node1.val != node2.val) {
				result = false;
				break;
			}
			node1 = node1.next;
			node2 = node2.next;
		}
		// 还原链表
		fast = pre;
		pre = null;
		while (fast != null) {
			next = fast.next;
			fast.next = pre;
			pre = fast;
			fast = next;
		}
		return result;
	}
}
